\documentclass{article}

\textheight 21 cm
\textwidth 14 cm
 
\topmargin -1mm
\marginparwidth 0mm
\evensidemargin 1.5 cm
\oddsidemargin 1.5 cm

\begin{document}
\pagestyle{plain}

\bibliographystyle{abbrv}

%\newtheorem{df}{Definition}
%\newtheorem{th}{Theorem}

\title{
\Huge
BinProlog 2006 11.x Professional Edition\\
Advanced BinProlog Programming and Extensions Guide
\vskip 5cm
}


\author{
\Large
  {\bf Paul Tarau}\\\\
\large
  BinNet Corp.\\
  WWW: http://www.binnetcorp.com
\normalsize
}


%\date{}

\vskip 5cm
\maketitle

\newpage
\section{Introduction to BinProlog}

BinProlog has been developed by Paul Tarau (http://www.cs.unt.edu/\~~tarau)
and is based on his BinWAM abstract machine,
a specialization of the WAM
for the efficient execution of binary logic programs.

BinProlog is a fast and compact Prolog compiler, based on the
transformation  of Prolog to binary clauses. The compilation technique
is similar to the Continuation Passing Style transformation used in
some ML implementations. BinProlog  is also probably the first 
Prolog system featuring dynamic recompilation of asserted predicates
(a technique similar to the one used in some object oriented 
languages like SELF 4.0),
and a very efficient segment preserving copying heap garbage collector.

Incorporating more than 15 years of research on compilation of Prolog and
logic programming based Internet development,
BinProlog is a robust and complete Prolog
implementation featuring both C-emulated execution
and generation of standalone applications
by compilation to C.

New features added in this edition of BinProlog include:

\begin{itemize}
\item Mobile code, multi-threading for Windows
\item Built-in, easy to use, high-level Internet programming tools (part of the BinNet Internet toolkit),
including CGIs and sockets
\item term-unification based high-level Linda server and client operations
\item packaging of BinProlog as a DLL with examples of calls from C
and Java
\item new, robust LogiMOO multiuser cooperative work environment (`grupware') on top of BinProlog's new Linda operations
(a BinNet Internet Server demo application)
\end{itemize}.  

\subsection{Contents of the BinProlog package}

BinProlog distributions contain a subset of the following directories.

\begin{verbatim}
+---doc
+---winbp - only available with Windows Visual C source version
+---src - only available with source license
+---progs
+---library
+---TCL
+---c_inter
+---pl2c
+---csocks
+---BP_DLL - only available with Windows versions
+---tests
+---bin
+---lib
\end{verbatim}

Prolog sources for the compiler and builtins
are in directory {\tt src} (only available with BinProlog source license).

BinProlog binary libraries are in directory lib.

The directory {\tt doc} contains ASCII, Latex, PostScript and HTML
versions of BinProlog documentation and a makefile to regenerate it.

The directory {\tt pl2c} contains
various project (*.pro) files
and a makefile for generating a standalone applications
through compilation to C.

The directory {\tt c\_inter} contains BinProlog's C-interface
and examples of embedding of BinProlog in C applications.

The directory {\tt TCL} contains a bidirectional client/server based
BinProlog to Tcl/Tk interface.

The directory {\tt BP\_DLL} contains a Prolog dynamic library with an
example of C application calling it (useful for
owners of source license).

The directory {\tt csocks} contains standalone socket code for
embedding in C programs serving as client or server components
interoperating with BinProlog.

In case you have BinProlog Full Source Edition, the directory src
contains makefiles for gcc and VCC batch files to rebuild the
sources after you make changes. Just go in directory src and type
make all or makeall.bat.

Please read the documentation files provided separately and visit
our ONLINE HELP SYSTEM at BinNet Corp.'s web site, for last minute
updates, demos and information about new features and components.

On Cygnus' CYGWIN gcc, type

  make all

which also works on normal Unix systems not requiring unusual flags.

On Linux PCs type

  make linux

On Solaris sparcs type

  make solaris

This will take care to generate the content of most of the directories.

Finally, the Full Source Edition also contains VCC 6.0 project files
in directory winbp, for working conveniently with the sources on a 
Windows NT workstation.

Alternatively, work on sources is now also supported for Cygnus gcc
as well as Linux and othe Unix platforms, through a complete set of
updated makefiles.


\subsection{Binarization}
BinProlog is a small, program-transformation based compiler. Everything is
converted to Continuation Passing Binary Clauses:

{\flushleft A rule like} 

\begin{verbatim}
  a(X):-b(X),c(X,Y),d(Y).
\end{verbatim}

{\flushleft becomes}

\begin{verbatim}
  a(X,Cont):-b(X,c(X,Y,d(Y,Cont))).
\end{verbatim}

{\flushleft A} fact like

\begin{verbatim}
  a(13).
\end{verbatim}

{\flushleft becomes}

\begin{verbatim}
  a(13,Cont):-true(Cont).
\end{verbatim}

{\flushleft A} predicate using metavariables like

\begin{verbatim}
  p(X,Y):-X,Y.
\end{verbatim}

{\flushleft becomes}

\begin{verbatim}
  p(X,Y,Cont);-call(X,call(Y,Cont))).
\end{verbatim}

{\flushleft with} true/1 and call/2 efficient builtins in BinProlog.

You can now try out in BinProlog  your own binary programs by using
\begin{verbatim}
::-
\end{verbatim}
instead of
\begin{verbatim}
:- 
\end{verbatim}
so that the preprocessor will not touch
them\footnote{Take care if you use your own binary clauses to keep always
the continuation as a last argument of the last embedded continuation `predicate'. Look at the {\tt asm/0} tracer how
BinProlog itself does this.}. Otherwise, from the outside, BinProlog
looks like any other Prolog.

Binarization allows a significant simplification of the Prolog engine,
which can be seen as specialization of the WAM for the execution of
Continuation Passing Binary Programs.

As a consequence, a very small emulator that often
fits completely in the cache of the processor, a more efficient new
data representation and some low-level optimizations make BinProlog
probably the fastest freely available C-emulated Prolog at this time
(136 million LIPS on a 2.4 GHz Pentium 4 Toshiba PC).

This means 3-5 times faster than C-Prolog, 2-3 times faster than
SWI-Prolog, 1.5-2 times faster than (X)SB-Prolog and close to C-emulated
Sicstus Prolog.

\subsection{Platforms supported}

\begin{verbatim}
Windows XP/2000/NT/95/98 (Visual C version, multi-threaded)
Windows XP/2000/NT/95/98 (Cygnus gcc version, using free cygwin b20 C compiler)
Linux-x86 gcc version
Solaris-sparc gcc version
Other 32 or 64 bit Unix platforms, upon customer request
\end{verbatim}

{\flushleft As}
 the implementation makes no assumption about machine word size it is
likely to compile even on very strange machines that have a C-compiler.
BinProlog's integers are inherited from the native C-system.
For example on DEC ALPHA or Itanium or G5 machines BinProlog has $64-3=61$ bit integers.
On 32-bit systems it has $32-2=30$ bit integers.
Floating point is double (64 bits) and it is guaranteed that computations
in Prolog will always give the same results as in the underlying C.
As a matter of fact BinProlog does not really know that it has floats
but how this happens is rather long to explain here.

\section{Using BinProlog}

\subsection{Consulting/compiling files}

BinProlog features a number of different compilation and consulting
methods as well as dynamic recompilation of consulted (interpreted) code
for fast execution.

\noindent The shorthand

\begin{verbatim}
   ?- [myFile].
\end{verbatim}

\noindent defaults to the last used compilation method applied to
{\tt myFile.pro} {\tt myFile.pl} or {\tt myFile}. Among them,
the default mcompile/1 compiling to memory and scompile/1 which
uses temporary *.wam files to quickly load files which have not been
changed. A good way to work with BinProlog is to make a "project" *.pro
file includeing its components, as in:

\begin{verbatim}
:-[myFile1].
:-[myFile2].
..............
\end{verbatim}

\noindent  The shorthand

\begin{verbatim}
    ?- ~my_file
\end{verbatim}

\noindent defaults to the last used {\em interpretation} method applied to
{\tt myFile.pro} {\tt myFile.pl} or {\tt myFile}.
For online information
on their precise behavior, do:

\begin{verbatim}
?-info(oconsult),info(consult),info(dconsult),info(sconsult).

oconsult/1: 
  reconsult variant, consults and overwrites old clauses

consult/1: 
  consults with possible duplication of clauses, allows 
  later dynamic recompilation

consult/2: 
  consult(File,DB) consults File into DB

dconsult/1: reconsult/1 variant, cleans up data areas, 
  consults, allowing dynamic recompilation

sconsult/1: 
  reconsult/1 variant: 
    cleans up data areas, consults, makes all static
\end{verbatim}

To control dynamic recompilation you can use {\tt dynco/1} with {\tt yes}
and {\tt no} as arguments or {\tt db\_ratio/1} to precisely specify
the ratio between calls and updateds to predicates which will
trigger moving it from interpreted to compiled representation
(default=10).

BinProlog uses R.A. O'Keefe's public domain tokeniser and parser and
write utilities (see the files read.pl, write.pl), DCGs and a
transformer to binary programs. It compiles itself in a dozen of seconds on todays
fast Pentium II/III machines.

The system has very fast (heap-based) {\tt copy\_term/2}, {\tt
findall/3} and {\tt findall/4} predicates, floating point, global
logical variables.

An original term compression technique \cite{TN94:PLILP} (joint work with
Ulrich Neumerkel) reduces heap-consumption and adds some extra speed .
Ulrich's iterative {\tt copy\_term/2} algorithm further accelerates
BinProlog's `copy-once' heap-based {\tt findall/3} and {\tt findall/4}
so that findall-intensive programs may run 2-3 times faster in
BinProlog than in other (even native code) implementations.

All data areas are now user configurable and garbage collected.

For permanent information BinProlog has a, dynamically growing/shrinking
garbage-collected data area, the {\em blackboard}, 
where terms can be stored and accessed
efficiently with a a 2-key hashing function using something like

\begin{verbatim}
?-bb_def(likes,joe,[any(beer),good(vine),vegetarian(food)]).
\end{verbatim}

and updated with something like

\begin{verbatim}
?-bb_set(likes,joe,nothing).
\end{verbatim}

or 

\begin{verbatim}
?-bb_rm(likes,joe).
\end{verbatim}

To get its value:

\begin{verbatim}
?-bb_val(likes,joe,What).
\end{verbatim}

BinProlog  has also backtrackable global variables,
with 2-keyed names.

Try:

\begin{verbatim}
?- Person=joe, friend#Person:=:mary, bb.
\end{verbatim}

and then
\begin{verbatim}
?- friend # joe:=:X.
\end{verbatim}

The blackboard can be used either directly or
through an assert-retract style interface.

The blackboard also gives constant-time sparse arrays and lemmas.
For example try:

\begin{verbatim}
?- for(I,1,99),bb_def(table,I,f(I,I)),fail.
?- bb.
\end{verbatim}

BinProlog  has Edinburgh behavior and tries to be close
to Sicstus and Quintus Prolog on the semantics of builtins
without being too pedantic on what's not really important.
Some ISO Prolog extensions (stream I/O) are now present
in BinProlog (see Appendix for a list of builtins) together
with their C-style equivalents.

All the basic Prolog utilities are now supported (dynamic clauses, a
metainterpreter with tracing facility, sort, setof, dynamic operators
floating point operations and functions).
BinProlog is one of the fastest Prolog systems around.
Naive reverse makes more than 136 million LIPS on a
Pentium 4 2.4GHz machine.
Member/2 and for/3 are also C-based builtins for improved performance.

Almost all the builtins are now expanded inline resulting in reduced
heap consumption and improved  performance.

A few programs (an automatic Tetris player, a knight-tour, an
OR-parallel simulator, Fibonacci, Tak with lemmas, a small neural-net
simulator backprop.pl) illustrate some of the new features. A few well-known
benchmarks have been added to help compare BinProlog with other
implementations.

On 32 bit machines BinProlog has 30 bit integer arithmetic,
{\em 64 bit floating point operations} and functions like
sin, cos, tan, log, exp, sqrt etc. (On 64 bit machines BinProlog supports 61 bit integer arithmetic).
Arithmetic operations can be used either through the is/2 interface\footnote{Is/2 now
accepts execution of any predicate of arity $n+1$ as a function
of arity $n$.}:

\begin{verbatim}
?- X is cos(3.14)+sin(0).
\end{verbatim}

or in relational form

\begin{verbatim}
?- cos(1,X).
\end{verbatim}

Note that you should use something like {\tt Y=3+4, X is 1+expr(Y)}
instead of {\tt Y=3+4, X is 1+Y} which will not work in compiled code.
BinProlog's is/2 commutes with constructors and evaluates arbitrary
functions (predicates returning results as their last argument), 
therefore something like 

\begin{verbatim}
  X is [cos(3.14),2+3]++[10*10,5-2].
\end{verbatim}

will return 
\begin{verbatim}
X=[-0.999999,5,100,3]
\end{verbatim}

Floating point has the same precision and semantics
as the type {\em double} in C.
Floating point operations are close in speed to emulated Sicstus.
To try them out use the toy neural-network simulator {\tt backprop.pl}.
This program uses also constant time arrays and is therefore
unusually fast compared to its execution in other Prologs like
Quintus or Sicstus.

\subsection{Using multiple logic engines}

A new (experimental) feature added starting with version 3.39 alows launching
multiple Prolog engines having their own stack groups (heap, local stack
and trail). An engine can be seen as an abstract data-type which
produces a (possibly infinite) stream of solutions as needed.
To create an engine use:

\begin{verbatim}
  % :-mode create_engine(+,+,+,-).
  create_engine(HeapSize,StackSize,TrailSize,Handle)
\end{verbatim}

The Handle is a unique integer denoting the engine for further
processing.
To `fuel' the engine with a goal and an expected answer variable
do:

\begin{verbatim}
  % :-mode load_engine(+,+,+).
  load_engine(Handle,Goal,AnswerVariable)
\end{verbatim}

No processing except the initialization of the
engine takes place and no answer
is returned with this operation. Think about it as simply puting
gas in your car.

To get an answer from the engine do:
\begin{verbatim}
  % :-mode ask_engine(+,-).
  ask_engine(Handle,Answer)
\end{verbatim}

%If you want to keep the answer for further processing before
%asking for the next one, use {\tt copy\_term/2} as the original 
%will go away as the engine backtracks. 
%Note that nothing nasty
%(as unsafe references to dead heap cells) happens even if you forget
%to do this, except that the bindings in the `master' engine will
%be undone. 

When the stream of answers reaches its end, {\tt ask\_engine/2}
will simply fail.

If for some reasons you are not interested in the engine anymore,
do

\begin{verbatim}
  % :-mode destroy_engine(+).
  destroy_engine(Handle)
\end{verbatim}

{\flushleft to} free the data areas alocated for the engine.
If you want to submit another query before using the
complet stream of answers, it is more efficient to reuse an
existing engine with {\tt load\_engine/3}, instead of
destroying it and creating a new one.

Try out the following example (see more in files 
{\tt library/engines, progs/engtest.pl}):

\begin{verbatim}
 ?-create_engine(256,64,64,E),
   load_engine(E,append(As,Bs,[A,B,B,A]),As+Bs),
   ask_engine(E,R1),write(R1),nl,
   ask_engine(E,R2),write(R2),nl,
   load_engine(E,member(X,[1,2,3]),X),
   ask_engine(E,R3),write(R3),nl,
   ask_engine(E,R4),write(R4),nl,
   destroy_engine(E).
\end{verbatim}

As engines will be assigned to real processors in future
multi-threaded implementations this reusability of a
given engine for execution of multiple goals is intended
to allow precise control to the programmer over the
resurces of a system. Preemptive multitasking
handled either with thread libraries, when available and efficient,
or by BinProlog itself otherwise, is planned in the near future.

This `super-scalar' performance improvement
can already be tested with the companion (Solaris 2.x only)
Linda implementation in directory {\tt multi} (see file
{\tt multi/myprogs/mcolor.pl}).

If an engine fails due to the overflow of a given data area,
it will warn you and fail. The warnings are disabled with
quietness levels higher than 6 (command line switch {\tt \-q6}).
This allows use of engines to quietly recover from ressource
errors.

For owners of BinProlog's C-source licenses, C-functions
with similar names and semantics as the predicates
described in this section are available
to allow embedding of multiple independent
Prolog engines in their C-applications.

\subsection{Findall/3 with multiple engines}

The file {\tt library/engines.pl} contains some examples
of how multiple engines can be used for implementing
for instance all-solution predicates. Here is a re-entrant
{\tt find\_all/3}.

\begin{verbatim}
find_all(X,Goal,Xs):-
  default_engine_params(H,S,T),
  find_all(H,S,T,X,Goal,Xs).

find_all(H,S,T,X,Goal,Xs):-
  create_engine(H,S,T,Handle),
  load_engine(Handle,Goal,X),
  collect_answers(Handle,Xs),
  destroy_engine(Handle).

collect_answers(Handle,[X|Xs]):-ask_engine(Handle,A),!,
  copy_term(A,X),
  collect_answers(Handle,Xs).
collect_answers(_,[]).

default_engine_params(128,32,32).
\end{verbatim}

\subsection{Standalone applications through compilation to C}

BinProlog allows to separately compile user
applications and just link them with the emulator library and the
C-ified compiler (see directory {\tt pl2c}).  This allows creation of
a fully C-ified application in a few seconds. 

Just type {\tt make PROJ=queens} in directory {\tt pl2c}.
The standalone application {\tt queens} is ready to be executed
by typing {\tt queens}.
The generated C-code can be seen in files
{\tt queens.h} and {\tt queens.c}.

Moreover, on systems with dynamic linking like Solaris 2.x 
true executables of size starting at about 6K can be created starting
with version 3.30 (see directory {\tt dynpl2c}).

We refer to \cite{tdb95rev}
for the details of this translation process.

If you define a predicate {\tt main/0} then your
executable will start directly from there instead
of the usual interactive top-level. Calling it with a high
quietness-level (i.e. command line switch {\tt \-q5}) will
suppress warnings and unwanted messages.

{\flushleft Normally} BinProlog starts execution from main/1:

\begin{verbatim}
   main(X):-...
\end{verbatim}

{\flushleft BinProlog's} shell
is nothing but such an application which
starts with a toplevel loop i.e. something like:

\begin{verbatim}
   main(X):-toplevel(X).
\end{verbatim}

{\flushleft You} can override this behavior, even
for the standard BinProlog system containing the predicate {\tt main/1} (which
starts the interactive top-level), by defining a predicate {\tt main/0} in your
program file. In this case, {\tt main/0} becomes the new starting point.

{\flushleft You} can bootstrap the compiler (if you own a source license), after modifying the 
{\tt *.pl} files by:

\begin{verbatim}
  ?- boot.
  ?- make.
\end{verbatim}

or, similarly for any other project having a top {\tt *.pro} file:

\begin{verbatim}
  ?-make(ProjectFile).
  ?-make(ProjectFile,Module).
\end{verbatim}

or

\begin{verbatim}
  ?-cmake(ProjectFile).
  ?-cmake(ProjectFile,Module).
\end{verbatim}

if you intend to generate C-code and possibly hide non-public predicates
inside a module.

{\flushleft This} allows to integrate your preferences and extensions
written in Prolog to the BinProlog kernel.

{\em {\flushleft Make} sure you keep a copy the original 
{\em wam.bp} in a safe place, in case things go wrong when you type}
\begin{verbatim}
  ?-boot.
\end{verbatim}

\subsection{Some limitations/features of BinProlog}

BinProlog is fairly close
to the ISO standard both syntactically and semantically.

We have passed Occam's razor on a few "features" of Prolog that are 
obsolete in modern programming environments and on some others that are,
in our opinion, bad software practice. These are usually unspecified by the ISO
standard, therefore this does not affect our ISO compliance.

Normally only one file at a time can be compiled in the interactive environment:

\begin{verbatim}
  ?-[myfile].
\end{verbatim}

or

\begin{verbatim}
  ?- compile(myfile).
\end{verbatim}

As BinProlog supports
an include directive:

\begin{verbatim}
:-[include1].
:-[include2].
....
\end{verbatim}

this is probaly the best way to work, in a stateless always clean
workspace. Note that, following the ISO standard, multiple includes
result in only one copy of the file being included.

BinProlog  allows consulting multiple files subject to
dynamic recompilation (use dconsult/1 to get something close
to SICStus/Quintus loading convention) or use command line switch
\-l4 to have this as default behavior for reconsult (with shorthand
{\tt \\~~file}).

With dynamically recompiled consulted code, listing of sources
and dynamic modification to any predicate is available while
average performance stays close to statically compiled code 
(usually within a factor of 2-3).

This suggest to make a project {\tt *.pro} file using a set of
include directives each refereing to a {\tt *.pl} file. 
When compiled to a file (by using the 
\begin{verbatim}
   ?-make(MyProject).
\end{verbatim}
command) a make-like memoing facility will avoid useless recompilation
of the included {\tt (*.pl)} files by creation of precompiled 
{\tt (*.wam)}
files. For large projects this is the recommended technique.
Creation of C-ified standalone files is also possible 
(see the {\tt pl2c directory}).

{\flushleft Programs} that work well can be added to the BinProlog kernel.
This avoids repeated recompilation of working code and predicates in the
kernel are protected against name clashing.

New programs can be loaded in the interactive environment.  When they
work well, they migrate to the kernel. You can prepare a good Makefile
to automate this job.  When everything is OK you can deliver it as a run-time-only application.
Releases after 3.30 contain a basic make facility which avoids
to recompile included {\tt *.pl} files when a newer {\tt *.wam} file exists.

Programs are searched with suffixes {\tt "", ".pl", ".pro"} in the directories
{\tt ., ../progs and ./myprogs}.

There's no limit on the number of files you can compile to disk:
\begin{verbatim}
  ?- compile(wam,[file1,file2,...],'application.bp').
\end{verbatim}

Now BinProlog does implement consult/1, reconsult/1 and listing/0 for
interpreted code but use.
See the file extra.pl for the implementation.
Similar to asserted but update-backtrackable, is BinProlog's {\em assumed code} (see the
next sections) i.e. intuitionistic and linear implication.

{\flushleft Here} are some other limitations/features:

\begin{itemize}
\item Clauses of a predicate must be grouped, unless overriden by multifile/1 or discontiguous/1 declarations).

\item ARITY is limited to 255.

\end{itemize}

\subsection{Garbage Collection}

A high performance copying heap garbage collector is implemented in versions 4.x and newer (thanks to
Bart Demoen and Geert Engels). {\tt nogc/0} switches it off,
{\tt gc/0} switches it on. Gc activation messages can be made
silent using quietness levels like {\tt \-q3} on the command-line,
(now the default).
Moreover, the blackboard, dynamic code space, the string space and the hashing table ARE garbage collected before loading a new program.

\subsection{Other BinProlog goodies and new predicates}

A few BinProlog specific predicates are available:

\begin{verbatim}
  restart/0 - cleans every data area
  cwrite/1  - fast but restricted write
  symcat/3  - returns a new symbol made from its arguments
  gensym/2  - forms a new name of the form name_counter
  sread/2   - reads from a name a (ground) term
  swrite/2  - writes a term to a name
  termcat/3 - adds its second argument as last argument 
              of its first argument and returns the new term
  term_chars/2-  converts between a ground term and its
              string representation
  not/1       - is a form of sound negation
  for/3       - as for instance in

              ?-for(I,1,5),write(I),nl,fail

              iterates over a failure driven loop.
\end{verbatim}

It is a good idea to take a look at BinProlog's {\tt *.pl} for
other builtin-or-library predicates before implementing them yourself.
The file {\tt write.pl} contain various output predicates like
\begin{itemize}
\item write/1
\item writeq/1
\item portray\_clause/1
\item print/1
\item display/1
\item ttyprint/1
\item ttynl/1
\end{itemize}

{\flushleft You} can extend BinProlog by adding new predicates to the file extra.pl
and then use the predicate {\tt boot/0} defined in the file co.pl to
generate a customized {\tt wam.bp} file which integrates your changes
when passed as a command line parameter to the {\tt bp} executable.

\subsection{Functional style higher-order programming}


BinProlog  integrates a number of useful higher-order
predicates working on deterministic, functional style predicates.
If your program is mostly functional the best thing is of course
to forget about logic programming and write it in Haskell.
However, with efficient implementatations of
map/3, foldl/4, foldr/4 and the call/N as builtins BinProlog
reduces the amount of extra argument book-keeping programmers
face. Sum/2 and prod/2, computing the sum and the product of
a list (now also builtins)
are good examples of this more compact
and fairly efficient higher-order programming style.

\begin{verbatim}
sum(Xs,R):-foldl(+,0,Xs,R).

prod(Xs,R):-foldl(*,1,Xs,R).
\end{verbatim}

Note that all functions (deterministic predicates returning result in their last argment)
can be used from is/2 which also commutes with constructors, i.e. something like

\begin{verbatim}
   X is [5+sum([1,2,3]),sum([10,20])].
\end{verbatim}

\subsection{Efficient findall based meta-programming}

BinProlog's {\tt findall/3} is so efficient that you can
afford (with some care) to use it instead of explicit
(and more painful) first-order programs as in:

\begin{verbatim}
% maplist with findall
maplist(Closure,Is,Os):-
  Closure=..L1,
  det_append(L1,[I,O],L2),
  P=..L2,
  findall(O,map1(P,I,Is),Os).

map1(P,I,Is):-member(I,Is),P.
\end{verbatim}

This can be used as follows:

\begin{verbatim}
?- maplist(+(1),[10,20,30],T).
=> T=[11,21,31]
\end{verbatim}

Note that constructing {\tt Closure} only once (although this 
may not be in any Prolog text-book!) is more efficient
than doing it at each step.

This {\em generator} based programming style puts nondeterminism
to work as a relatively clean and encapsulated form of
iteration.

The predicate {\tt gc\_call(Goal)} defined in the file {\tt lib.pl}
executes Goal in minimal space.  It is explained in the Craft of Prolog
by R.A. O'Keefe, MIT Press.
Do not hesitate to use it. BinProlog offers a very fast, heap-oriented
findall, so you can afford to use {\tt gc\_call}. In good hands, it is
probably faster than using assert/retract and preventing
space consumption is always a good idea despite the fact
that BinProlog 6.25's efficient heap garbage collector will
get your memory back anyway.

\subsection{Builtins}

BinProlog has large number of builtins with semantics
(intended to be) close to SICStus and QUINTUS Prolog.

We refer to the automatically generated info file in Appendix
for short definitions and examples of uses of BinProlog's
documented builtins.

\section{Macro processing}

Two forms of macro processing facilities are available in BinProlog.
One is {\tt term\_expansion/2} allowing to define toplevel
operators (like the DCG arrow) to be expanded to whatever the
user wants to. Starting with version 5.82, {\tt term\_expansion/2}
facts can be either assumed or asserted.
Another is compile-time execution {\tt \#\#/1} which
executes arbitrary goals once while compiling it. For instance, it

\begin{verbatim}
pi2(Y):- ##((X is 2*asin(1),Y is X*X)).
\end{verbatim}

arithmetic operations
will be executed once while loading the file, instead of
being executed each time {\tt pi2} is called. 

Note that both operations should only call predicates
which are {\em already} defined,
before the compilation starts.

\section{Inspecting some BinProlog internals}

{\flushleft You} can generate a kind of intermediate WAM-assembler by

\begin{verbatim}
  ?- compile(asm,[file1,file2,...],'huge_file.asm').
\end{verbatim}

{\flushleft A} convenient way to see interactively the sequence of program
transformations BinProlog is based on is:

\begin{verbatim}
?- asm.
a-->b,c,d.
^D

DEFINITE:
a(A,B) :- 
        b(A,C),
        c(C,D),
        d(D,B).

BINARY:
a(A,B,C) :- 
        b(A,D,c(D,E,d(E,B,C))).

WAM-ASSEMBLER:
clause_? a,3
firstarg_? _/0,6
put_structure d/3,var(4-4/11,1/2)
write_variable put,var(5-5/10,1/2)
write_value put,var(2-2/6,2/2)
write_value put,var(3-3/7,2/2)
put_structure c/3,var(3-8/14,1/2)
write_variable put,var(2-9/13,1/2)
write_value put,var(5-5/10,2/2)
write_value put,var(4-4/11,2/2)
execute_? b,3
\end{verbatim}


\section{Compiling to C}

Partial C-ification \cite{tdb95} is a translation framework which
`does less instead of doing more' to improve performance of emulators
close to native code systems.

Starting from an emulator for a language L written in C, we translate
to C a
subset of its instruction set (usually frequent and fine-grained
instructions which are executed in contiguous sequences)
and then simply use a compiler for C
to generate a unique executable program.

A translation threshold allows the programmer
to empirically fine-tune the C-ification
process by choosing the length of the
emulator instruction sequence, starting from which,
translation is enabled. The process uses
a reasonable default value and can be easily controlled
by the programmer

\begin{verbatim}
:-set_c_threshold(Min,Max).
\end{verbatim}

will ensure that only emulated sequences of length between
Min and Max get translated to C. This allows to handle gracefully
the size/speed tradeoff. 

Communication between the run-time system (still
under the control of the emulator) and the C-ified
chunks is handled as follows.

The emulated code representation of a given
program (in particular the compiler itself)
is mapped to a C
data structure which allows exchange of symbol table
information at link time.

To be able to call a C-routine from the emulator we have to
know its address. Unfortunately, the linker is the only one that knows
the eventual address of a C-routine.
A simple and fully portable technique to plug the address of a 
C-routine into the byte code is to C-ify the byte-code 
of the emulator into a huge C array of records, containing the
symbolic address of the C-chunks. After compilation, and linking
with the emulator, the 
linker will automatically resolve all the missing addresses and 
generate warnings for the missing C-routines.

This is compiled together with the C-code of the emulator
to a stand alone executable with
performance in the range between
pure emulators and native code implementations.

The method ensures a strong operational equivalence between
emulated and translated code which share exactly the same
observables in the run-time system.

An important characteristic is easy debugging of the resulting
compiler, coming from the full sharing
of the run-time system between emulated and compiled code
and the following property we call
{\em instruction-level compositionality}:
if every translated instruction has the same observable effect on
a (small) subset of
the program state (registers and a few data areas)
in emulated and translated mode, then 
arbitrary sequences of emulated and translated
instructions are operationally equivalent.

Currently C-ification covers term creation on the heap
and  frequently used
inline operations which can be processed
in Binary Prolog before calling the `real goal' in the body.

Chunks containing small built-ins that do not 
require a procedure call will
generate `leaf-routines' in C (which are called
efficiently and do not use stack space).

On the other hand large built-ins implemented as macros in the emulator
would make code size explode.
Implementing them as functions  to be called
from the C-chunk would
require code duplication and it would destroy
the leaf-routine discipline
which is particularly rewarding on Sparcs.
We have chosen
to implement them through an
abstraction with a coroutining flavor: {\em anti-calls}.
Note that calling a built-in from a C-chunk is operationally
equivalent to the following sequence:

\begin{itemize}
\item return from the chunk, 
\item execute the built-in in the emulator (usually a macro),
\item call a new leaf-routine to resume the work left from the
      previous leaf-routine.
\end{itemize}

Overall, anti-calls can be seen as form of coroutining
(jumping back and forth) between native
and emulated code.
Anti-calls can be implemented with the direct-jump technique
even more efficiently,
although for portability
reasons we have chosen a conventional return/call sequence,
which is still fairly efficient
as a return/call costs the same as a call/return.
Moreover, this allows the chunks to remain leaf-routines,
while delegating
overflow and signal handling
to the emulator. Note that
excessively small chunks created as result
of anti-calls are removed by an optimizing step
of the compiler with the net result
that such code will be completely left to
the emulator. This is of course
{\em more compact} and provable to be {\em not
slower} than its fully C-expanded alternative.

\subsection{Performance of C-ified code}

The speed-up clearly depends on the amount of C-ification
and on the statistical importance of C-ified code in
the execution profile of a program (see figure \ref{bm}).
We have noticed between 10-20\% speed increase for
programs which take advantage of C-ified code moderately,
As these programs spend only 20-30\% of their time
in C-ified sequences performances are expected
to scale correspondingly when
we extend this approach to the full BinProlog 
instruction set and implement low-level
gcc direct jumps instead
of function calls and anti-calls.


\begin{figure}
\begin{center}
\begin{tabular}{||l||r|r||r|r||}
\hline
\hline
\multicolumn{1}{|c|}{{\em Bmark/Compiler}} &
  \multicolumn{1}{c|}{emBP} &
  \multicolumn{1}{c|}{C-BP} &
  \multicolumn{1}{c|}{emSP} &
  \multicolumn{1}{c|}{natSP} \\
\hline
\hline
 NREV (KLIPS) & 445 &455 &412 &882   \\\hline
 CAL (ms) & 490 &310  &590  &310   \\\hline
 FIBO (ms) & 1730& 1320 &1400 &800  \\\hline
 TAK (ms) & 610 &470 &400 &180  \\\hline
 SEMI3 (ms) & 1810 &1410 &1810 &1310  \\\hline
 QUEENS (ms) & 3170 &2220 &2840 &1070  \\\hline
\hline
\hline
\end{tabular} \\
\medskip
\caption{Performance of emulated (emBP) and partially
C-ified BinProlog 3.22 (C-BP)
compared to emulated (emSP) and native (natSP) SICStus 2.1\_9 
on a Sparc 10/20).
 \label{bm}}
\end{center}
\end{figure}

Code-sizes for C-ified BinProlog executables (dynamically linked
on Sparcs with Solaris) are usually even
smaller than `compact' Sicstus code
which uses classical instruction
folding (a few hundreds of opcodes) to speed-up the emulator.

The following table shows some code-size/execution-speed 
variations with respect to the threshold for
the semi-ring ({\tt SEMI3}) benchmark. Clearly, excessively
small chunks can influence adversely not only on
size but also on speed. Something like threshold=20,
looks like a practical optimum
for this program.

{\small
\begin{verbatim}
threshold:   0    4    8    20  30  1000 emBP emSP natSP
size:  (K)  34.5 32.2 29.9 16.3 13.1 12.9  4.8 22.0 31.9
speed: (ms) 1480 1430 1440 1450 1810 1790 1800 1810 1310
\end{verbatim}
}


\section{The Blackboard}

A new interface has been added to separate backtrackable
and surviving uses of blackboard objects so this primitive
and the def/3, set/3, rm/2 of previous versions although still
available should be replaced either with:

\begin{itemize}
\item global logical variables
\item garbage-collectible permanent objects.
\end{itemize}

\subsection{Global logical variables}

\begin{verbatim}
   Syntax: A#B:=:X, or lval(A,B,X).
\end{verbatim}

{\flushleft where X} is any term on the heap. 
It has simply a global name {\tt A\#B} i.e. an
entry in the hashing table with keys A and B.  The address in the table
(C-pointers are the same as logical variables in BinProlog) is trailed
such that on backtracking it will be unbound (i.e. point to itself).
Unification with a logical global variable is possible at any point in the program which knows the `name' A\#B.

Although a global logical variable cannot be changed it can be
further instantiated as it happens to ordinary Prolog terms.
Backtracking ensures they vanish so that no unsafe reference can be
made to them.

The program lq8.pl is an efficient 8-queens program using
global logical variables to simulate the chess-board.

\subsection{Garbage-collectible permanent objects.}

On the other hand, if {\tt bb\_def/3} or {\tt bb\_set/3} is used to name objects on the
blackboard, they "survive" backtracking and can afterwards be retrieved as
logical variables using {\tt bb\_val/3}.

\begin{verbatim}
bb_def/3    (i,i,i) defines a value
bb_set/3    (i,i,i) updates a value
bb_rm/2     (i,i) removes a value
bb_val/3    (i,i,o) retrieves the value
\end{verbatim}

They are quite close to the {\tt recorda/recordz} family of other
Prologs although they offer better 2-key indexing, are simpler and can
be used to do much more things efficiently.

You can look to the program {\tt progs/knight.pl} on how to use them to
implement in a convenient and efficient way programs with backtrackable
global arrays.

They can be used to save information that survives backtracking in a
way similar to other Prolog's {\tt assert} and {\tt retract} and are safe
with respect to garbage collection of the blackboard.

The predicate {\tt bb\_list/1} gives the content of the blackboard as a heap object (list), while {\tt bb/0} simply prints it out.

These predicates offer generally faster and more flexible management of
dynamic state information than other Prolog's dynamic databases.


\subsection{Assert and retract}

For compatibility reasons
BinProlog has them, implemented on top of the more efficient
blackboard manipulation builtins.
With BinProlog  and dynamic recompilation however,
some applications might be faster overall by using
assert and retract, depending on the update/call ratio of
dynamic predicates (you can use command line switch -r to
change this). Try both compiling and reconsulting 
the benchmark progs/assertbm.pl
to have an estimate of the speed of these operations on your
machine.

This is an approximation of other Prologs assert and retract predicates.
It tries to be close to Sicstus and Quintus with their semantics.

If you want maximal efficiency for highly volatile data, use directly 
{\tt bb\_def/3, bb\_set/3, bb\_val/3, bb\_rm}
They give you access to a very fast hashing table 

\begin{verbatim}
   <key1,key2> --> value,
\end{verbatim}

the same that BinProlog uses internally for indexing by predicate and
first argument.  They are close to other Prolog's `record' family,
except that they do even less.

When using dynamic predicates it is a good idea
to declare them with {\tt dynamic/1}
although {\tt asserts} will now be accepted even without such a
declaration. To define dynamic code in a file you compile,
dynamic declarations are mandatory.

To activate an asserted predicate it is a good idea
to alway call it with

\begin{verbatim}
	?-metacall(Goal).
\end{verbatim}

{\flushleft instead} of 

\begin{verbatim}
	?- Goal.
\end{verbatim}

However, this is not a strong requirement anymore,
as an important number of users were unhappy with this restriction.

The dynamic predicates are:

\begin{verbatim}
assert/1
asserta/1
assertz/1

retract/1
clause/2
metacall/1
abolish/2
\end{verbatim}

You can easily add others or improve them by looking to the sources
in the file {\tt extra.pl}.

\subsection{Multiple dynamic databases}

BinProlog  features multiple dynamic databases. Only one is
active at a time and you can switch among them with {\tt set\_db/1}
or even move one over another with {\tt db\_move/2}.

Use info/1 to obtain more information on one of the following:

\begin{verbatim}
current_db/1-built_in
set_db/1-built_in
db_abolish/2-built_in
db_assert/2-built_in
db_asserta/2-built_in
db_asserted/2-built_in
db_assertz/2-built_in
db_clause/3-built_in
db_clean/0-built_in
db_clean/1-built_in
db_head/2-built_in
db_move/2-built_in
db_ratio/1-built_in
db_retract/2-built_in
db_retract1/2-built_in
db_retractall/2-built_in
\end{verbatim}

\subsection{The blackboard as an alternative to assert and retract}

Designed in the early stages of Prolog, assert and retract have been
overloaded with different and often conflicting requirements. They try
to be both the way to implement permanent data structures for global
state information, self-modifying code
and tools for Prolog program management. This created
not only well-known semantical but also expressiveness and efficiency
problems.

This unnecessary overloading is probably due to some of their intended uses in interpreted Prologs like implementing the {\tt consult/1} and 
{\tt reconsult/1} code-management predicates that can be replaced today by general purpose makefiles. As a consequence, their ability to express sophisticated data structures is very limited due mostly to unwanted copying operations (from heap to dynamic code area and back) and due to their non-backtrackable behavior.

For example, to ensure indefinite number of uses of an asserted clause most Prologs either compile it on the fly or do some form of copying (usually twice: when asserting and when calling or retracting). This is not only a waste of resources but also forbids use of asserted clauses for dynamically evolving global objects containing logical variables, one of the most interesting and efficient data structure tricks in Prolog. Worst, variables representing global data structures have to be passed around as extra arguments, just to bore programmers and make them dream about 
inheritance and objects oriented languages.
This also also creates error prone maintenance problems. Just think about adding a new seventh argument to a 10-parameter Prolog predicate having 10 clauses and being called 10 times.

Those are the main
reasons for the re-design of these operations using
BinProlog's blackboard.

Efficient access to objects on the blackboard or part of them is based on an efficient 2-key hashing table, internal to BinProlog's run-time system.



\subsection{Copying primitives}
{\tt Copy\_term/2} is Prolog's usual primitive extended to copy objects from the heap and also from blackboard to the current top of the heap. We refer to
\cite{Tarau92:ECO} for the implementation and memory management aspects of
these primitives.

{\tt Save\_term/2} copies an object possibly distributed over the heap  and the blackboard to a new blackboard object. It also takes care not to copy parts of the object already on the blackboard.

Remark that having known modes and argument types helps in the case of
partial evaluation or type inference systems.
Separating Prolog's asserts two main functions (naming+copying) in
lower level operations allows program transformers to go {\em inside}
more complex blackboard operations and possibly use the typing and mode information that comes from def/3, set/3 and val/3 to infer it for other predicates.

\subsection{An useful Prolog extension: bestof/3}

{\tt Bestof/3} is missing in other Prolog implementations we
know of.  BinProlog's {\tt bestof/3} works like {\tt findall/3}, but
instead of accumulating alternative solutions, it selects successively
the {\em best} one with respect to an arbitrary {\em total order}
relation. If the test succeeds the new answer replaces the previous
one. At the end, either the query has no answers, case in which {\tt
bestof} fails, or an answer is found such that it is better than every
other answer with respect to the total order. The proposed syntax is
{\em Note that use bestof requires a \verb~:-[library(high)]~ include command.}

\begin{verbatim}
   ?-bestof(X,TotalOrder,Goal)
\end{verbatim}

At the end, X is instantiated to the best answer. For example, the maximum of a list of integers can be defined simply as:

\begin{verbatim}
    max(Xs,X):-bestof(X,>,member(X,Xs)).
\end{verbatim}

The following is an efficient implementation
implementation using the blackboard.

\begin{verbatim}
% true if X is an answer of Generator such that
% X Rel Y for every other answer Y of Generator
bestof(X,Closure,Generator):-
  copy_term(X,Y),
  Closure=..L1,
  det_append(L1,[X,Y],L2),
  Test=..L2,
  bestof0(X,Y,Generator,Test).

bestof0(X,Y,Generator,Test):-
  inc_level(bestof,Level),
  Generator,
  update_bestof(Level,X,Y,Test),
  fail.
bestof0(X,_,_,_):-
  dec_level(bestof,Level),
  val(bestof,Level,X),
  rm(bestof,Level).

% uses Rel to compare New with so far the best answer
update_bestof(Level,New,Old,Test):-
  val(bestof,Level,Old),!,
  Test,
  bb_set(bestof,Level,New).
update_bestof(Level,New,_,_):-
  bb_let(bestof,Level,New).

% ensure correct implementation of embedded calls to bestof/3
inc_level(Obj,X1):-val(Obj,Obj,X),!,X1 is X+1,bb_set(Obj,Obj,X1).
inc_level(Obj,1):-bb_def(Obj,Obj,1).

dec_level(Obj,X):-val(Obj,Obj,X),X>0,X1 is X-1,bb_set(Obj,Obj,X1).
\end{verbatim}

{\flushleft Note} that precomputation of Test in bestof/3 before calling the
workhorse bestof0/4 is much more efficient than using some form
of apply meta-predicate inside bestof0/4.

\subsection{Blackboard based abstract data types}

We will describe some simple utilizations of the blackboard to implement efficiently some basic abstract data types.
They all use the {\tt saved/2} predicate instead of {\tt save\_term/2}. 
{\tt Saved/2} does
basically the same work but also makes a call to the blackboard garbage
collector if necessary. The reader can find the code in the file {\tt lib.pl}
of the BinProlog distribution.

\subsubsection{Blackboard based failure surviving stacks/queues}

A very useful data structure that is implemented with the blackboard is
a stack/queue that survives failure but still allows the programmer to use some of the nice properties of logical variables. It is implemented through a set of C-based builtins in BinProlog  and used among other things
in the implementation of BinProlog's dynamic code.

\begin{verbatim}
addq/3 adds to end of persistent queue as in addq(key1,key2,33).
pushq/3 adds to beginning of a persistent queue
cpopq/3 pops (copy of) first element of the queue
cmembq/3 backtracks over (copies of) members of a queue
cdelq/4 deletes first matching element from a queue
\end{verbatim}

See examples of use in the automatically generated Appendix.

\subsubsection{Constant time vectors}

Defining a vector is done initializing it to a given Zero
element. The {\tt vector\_set/3} update operation uses {\tt saved/2}, therefore
the old content of vectors is also subject to garbage collection. 

\begin{verbatim}
vector_def(Name,Dim,Zero):- Max is Dim-1,
  for(I,0,Max), % generator for I from 0 to Max
    bb_let(Name,I,Zero),
  fail.
vector_def(_,_,_).

vector_set(Name,I,Val):-bb_set(Name,I,Val).

vector_val(Name,I,Val):-bb_val(Name,I,Val).
\end{verbatim}

Building multi-dimensional arrays on these vectors is straightforward, by
defining an index-to-address translation function.

The special case of a high-performance 2-dimension (possibly sparse) global array can be handled conveniently by using {\tt bb\_def/3, bb\_set/3, bb\_val/3} as in:

\begin{verbatim}
global_array_set(I,J,Val):-bb_set(I,J,Val).
\end{verbatim}

\subsection{Blackboard based problem solving}

\subsubsection{A complete knight tour}

The following is a blackboard based complete knight-tour, adapted from
Evan Tick's well known benchmark program.

\begin{verbatim}
% recommended use: ?-go(5).
go(N):-
	time(_),
	  init(N,M),             % prepare the chess board
	  knight(M,1,1),!,       % finds the first complete tour
	time(T),
  write(time=T),nl,statistics,show(N). % shows the answer

% fills the blackboard with free logical variables
% representing empty cell on the chess board
init(N,_):-
  for(I,1,N),     % generates I from 1 to N nondeterministically
    for(J,1,N),   % for/3 is the same as range/3 in the Art of Prolog
      bb_def(I,J,_NewVar),  % puts a free slot in the hashing table
  fail.
init(N,M):-
  M is N*N.                 % returns the number of cells

% tries to make a complete knight tour
knight(0,_,_) :- !.
knight(K,A,B) :-
  K1 is K-1,
  val(A,B,K),  % here we mark (A,B) as the K-th cell of the tour
  move(Dx,Dy), % we try a next move nondeterministically
  step(K1,A,B,Dx,Dy).

% makes a step and then tries more
step(K1,A,B,Dx,Dy):-
    C is A + Dx,
    D is B + Dy,
    knight(K1,C,D).

% shows the final tour
show(N):-
  for(I,1,N),
    nl,
    for(J,1,N),
      val(I,J,V),
      write(' '),X is 1-V // 10, tab(X),write(V),
  fail.
show(_):-nl.

% possible moves of the knight
move( 2, 1). move( 2,-1). move(-2, 1). move(-2,-1).
move( 1, 2). move(-1, 2). move( 1,-2). move(-1,-2).
\end{verbatim}

Constant time access in this kind of problems to cell(I,J) is essential for
efficiency as it is the most frequent operation.
While the blackboard based version takes 39s in BinProlog for a 5x5 squares chess board, an equivalent program representing the board with a list of lists takes 147s in BinProlog, 167s in emulated Sicstus 2.1 and 68 seconds in native Sicstus 2.1. Results are expected to improve somewhat with binary trees or functor-arg representation of the board but they will still remain worse than with the blackboard based sparse array, due to their relatively high log(N) or constant factor. Moreover, representing large size (possibly updatable!) arrays with other techniques is prohibitively expensive and can get very complicated due to arity limits or tree balancing as it can see for example in the Quintus library.

\subsubsection{A lemma based TAK}

The following tak/4 program uses lemmas to avoid heap explosion in the case of
of a particularly AND intensive program with 4 recursive calls, a problem particularly severe in the case of the continuation passing binarization that BinProlog uses to simplify the WAM. To encode the 2 first arguments in a unique integer some bit-shifting is needed as it can be seen in {\tt tak\_encode/3}. To avoid such problems, multi-argument hashing 
with BinProlog 6.25's {\tt term\_hash/3} can be used.

\begin{verbatim}
tak(X,Y,Z,A) :- X =< Y, !, Z = A.
tak(X,Y,Z,A) :-
        X1 is X - 1,    
        Y1 is Y - 1,    
        Z1 is Z - 1,    
        ltak(X1,Y,Z,A1), 
        ltak(Y1,Z,X,A2), 
        ltak(Z1,X,Y,A3), 
        ltak(A1,A2,A3,A).

ltak(X,Y,Z,A):-
        tak_encode(X,Y,XY),
        tak_lemma(XY,Z,tak(X,Y,Z,A),A).

tak_encode(Y,Z,Key):-Key is Y<<16 \/ Z.                
tak_decode(Key,Y,Z):-Y is Key>>16, Z is Key <<17>>17 .

%optimized lemma <P,I,G> --> O (instantiated executing G)
tak_lemma(P,I,_,O):-val(P,I,X),!,X=O.
tak_lemma(P,I,G,O):-G,!,def(P,I,O).

go:-    statistics(runtime,_), 
        tak(24,16,8,X),
        statistics(runtime,[_,T]),statistics, 
        write([time=T,tak=X]), nl.

\end{verbatim}

We hope that we showed the practicality of BinProlog's blackboard for basic
work on data structures and problem solving.

BinProlog's blackboard primitives make a clear separation between the {\em copying} and the {\em naming} intent overloaded in Prolog's assert and retract.

Our blackboard primitives give most of the time simpler and more efficient solutions to current programming problems than assert and retract while being closer to a logical semantics and more cooperative to partial evaluation.

Look into file dtak.pl for a Delphi-memoing version of the
same program (a probabilistic automatic memoing method).

\section{Continuations as first order objects}

\subsection{Continuation manipulation vs. intuitionistic/linear implication}

Using intuitionistic implication we can write in BinProlog:

\begin{verbatim}
    insert(X, Xs, Ys) :- 
        paste(X) => ins(Xs, Ys). 

    ins(Ys, [X|Ys]) :- paste(X).
    ins([Y|Ys], [Y|Zs]):- ins(Ys, Zs).
\end{verbatim}

{\flushleft used} to nondeterministically insert an element in a list,
the unit clause {\tt paste(X)} is available only within the scope of the
derivation for {\tt ins/2}. This gives:

{\small
\begin{verbatim}
?- insert(a,[1,2,3],X).
X=[a,1,2,3];

X=[1,a,2,3];

X=[1,2,a,3];

X=[1,2,3,a]
\end{verbatim}
}

With respect to the corresponding Prolog program
we are working with a simpler
formulation in which the element to be inserted does not have to percolate
as dead weight throughout each step of the computation, only to be used in
the very last step. We instead clearly isolate it in a global-value manner,
within a unit clause which will only be consulted when needed, and which
will disappear afterwards.

Now, let us imagine we are given the ability to write part of a proof state
context, i.e., to indicate in a rule's left-hand side not only the
predicate which should match a goal atom to be replaced by the rule's body,
but also which other goal atom(s) should surround the targeted one in
order for the rule to be applicable. 

Given this, we could write, using BinProlog's {\tt @@}
(which gives in its second argument the current continuation) a program
for {\tt insert/3} which strikingly resembles the intuitionistic
implication based program given above:

{\small
\begin{verbatim}
insert(X,Xs,Ys):-ins(Xs,Ys),paste(X).

ins(Ys,[X|Ys]) @@ paste(X).
ins([Y|Ys],[Y|Zs]):-ins(Ys,Zs).
\end{verbatim}
}

{\flushleft Note} that the element to be inserted is not passed to the recursive
clause of the predicate {\bf ins/2} (which becomes therefore simpler),
while the unit clause of the predicate {\bf ins/2} will communicate
directly with {\bf insert/3} which will directly `paste' the appropriate
argument in the continuation.
 
In this formulation, the element to be inserted is first given as
right-hand side context of the simpler predicate {\tt ins/2}, and this predicate's
first clause consults the context {\tt paste(X)} only when it is time to place it within the output list,
i.e. when the fact 
\begin{verbatim}
ins(Ys,[X|Ys]),paste(X)
\end{verbatim}
is reached. 

Thus for this example, we can also obtain the expressive power of
intuitionistic/linear implication
by this kind of (much more efficient)
direct manipulation of BinProlog's
first order continuations.

\section{Direct binary clause programming and full-blown continuations}

BinProlog  supports direct manipulation of binary clauses
denoted 

\begin{verbatim}
   Head ::- Body.
\end{verbatim}

{\flushleft They} give full power to the knowledgeable programmer on
the future of the computation. Note that such a facility is not
available in conventional WAM-based systems where continuations
are not first-order objects.

We can use them to write programs like:

{\small
\begin{verbatim}
  member_cont(X,Cont)::-
    strip_cont(Cont,X,NewCont,true(NewCont)).
  member_cont(X,Cont)::-
    strip_cont(Cont,_,NewCont,member_cont(X,NewCont)).

  test(X):-member_cont(X),a,b,c.
\end{verbatim}
}

{\flushleft A} query like
{\small
\begin{verbatim}
  ?-test(X).
\end{verbatim}
}

{\flushleft will} return {\tt X=a; X=b; X=c; X= whatever follows from the calling point of test(X)}. 

{\small
\begin{verbatim}
catch(Goal,Name,Cont)::-
   lval(catch_throw,Name,Cont,call(Goal,Cont)).

throw(Name,_)::-
   lval(catch_throw,Name,Cont,nonvar(Cont,Cont)).
\end{verbatim}
}

{\flushleft where} {\tt lval(K1,K2,Val)} is  a BinProlog
primitive which unifies {\tt Val} with a backtrackable global logical
variable accessed by hashing on two (constant or variable) 
keys {\tt K1,K2}.

This allows for instance to avoid execution of the infinite {\tt loop/0}
from inside the predicate {\tt b/1}.

{\small
\begin{verbatim}
loop:-loop.

c(X):-b(X),loop.

b(hello):-throw(here).
b(bye).

go:-catch(c(X),here),write(X),nl.
\end{verbatim}
}

Notice that due to its simple {\em translation semantics} this program
still has a first order reading and that BinProlog's {\tt lval/3}
is not essential as it can be emulated by an extra argument passed
to all predicates.

Although implementation of {\tt catch} and {\tt throw} requires full-blown
continuations, we can see that at user level, ordinary
clause notation is enough.


\subsection{Standard Prolog catch and throw}

BinProlog  implements also Standard Prolog's catch/throw mechanism,
using a similar technique (thanks to Bart Demoen!), which works as follows:

{\small
\begin{verbatim}
catch(Goal,Ball,Do):-
  execute Goal
  on throw(Term): look for closest catch
     copy Term
     undo bindings until call to catch; remove choices
     unify with Ball
        if fail: throw Ball again
        if succeed: call Do, continuation of catch goal
\end{verbatim}
}

Note that our continuations and linear assumption based implementation
ensures constant time execution of catch and throw, without actual
stack scanning.

{\small
\begin{verbatim}
Example:

?-catch((member(X,[1,2,3]),throw(my_term(X))),my_term(Y),println(caught(Y))).
caught(1)
X=_x2352,
Y=1
\end{verbatim}
}

\subsection{Ancestor cut}

For enhanced control
BinProlog  implements a form of ancestor cut,based on the following
3 built-ins:
{\small
\begin{verbatim}
get_neck_cut/1: gets the address of a choice point 
                (to be use before the first not-inlined goal)

get_deep_cut/1: gets the address of a choice point 
                (to be use after the first not-inlined goal)

cut_to/1:       cuts to a given choice-point

untrail_to/1:   removes bindings up to a given choice-point
\end{verbatim}
}

Together with continuation manipulation and linear assumptions, the use of these built-ins allows a source-level implementation of catch and throw.

Another example of use, committing to the current resolution branch and cutting off
all the alternatives up to toplevel, is written simply as:

{\small
\begin{verbatim}
commit :-
  assumed(catchmarker('$commit',Do,Choice,_)),
  cut_to(Choice), Do.
\end{verbatim}
}

\section{Backtrackable destructive assignment}

\subsection{Updatable logical arrays in Prolog: fixing the semantics of {\tt setarg/3}}

Let us recall that {\tt setarg(I,Term,Value)}  installs
{\tt Value} as the {\tt I\-th} argument of {\tt Term} and takes care to
put back the old value found there on backtracking.

{\tt Setarg/3} is probably
the most widelly used 
(at least in SICStus, Aquarius, Eclipse, ProLog-by-BIM, BinProlog), 
incarnation of backtrackable mutable arrays (overloaded
on Prolog's universal {\em term} type).

Unfortunately {\tt setarg/3} lacks
a logical semantics and is implemented differently in
in various systems. This is may be the reason
why the standardization (see its absence from the Prolog ISO Draft)
of {\tt setarg/3}
can hardly reach a consensus in the predictable future.

Ideally, {\tt setarg/3} should work as if a new term
(array) had been created
identical to the old one, except for the given element.
There's no reason to `destroy' a priori the content of the updated
cell or to make it subject to ugly side effects. Should this have
to happen for implementation reasons, a run-time error should
be produced, at least, although
this is not the case in any implementation
we know of.

Let us start with an inefficient but fairly clean array-update
operation, {\tt setarg/4}.

\begin{verbatim}
setarg(I,OldTerm,NewValue,NewTerm):-
  functor(OldTerm,F,N),
  functor(NewTerm,F,N),
  arg(I,NewTerm,NewValue),
  copy_args_except_I(N,I,OldTerm,NewTerm).

copy_args_except_I(0,_,_,_):-!.
copy_args_except_I(I,I,Old,New):-!,I1 is I-1,
  copy_args_except_I(I1,I,Old,New).
copy_args_except_I(N,I,Old,New):-N1 is N-1,arg(N,Old,X),arg(N,New,X),
  copy_args_except_I(N1,I,Old,New).
\end{verbatim}

We can suppose that functor and arg are specified by a (finite)
set of facts describing their behavior on
the signature of the program. For a given program,
we can obviously see setarg/4 as being
specified similarly by a finite set of facts. 

Furthermore,suppose that all
uses of setarg/3 are replaced by calls to setarg/4 with the new states
passed around with DCG-style chained variables.

This looks like a good definition of the intended meaning of
a program using setarg/3.

We will show that actual implementations (Sicstus and BinProlog)
can be made to behave accordingly to this semantics through a
small, source level wrapping into a suitable ADT.

Let 
\begin{verbatim}
'$box'/1
\end{verbatim}
be a new functor not in the signature of any
user program. By defining

\begin{verbatim}
safe_arg(I,Term,Val):-arg(I,Term,'$box'(Val)).

safe_setarg(I,Term,Val):-setarg(I,Term,'$box'(Val)).
\end{verbatim}

Using 
\begin{verbatim}
'$box'/1
\end{verbatim}
in {\tt safe\_arg/3} ({\tt safe\_setarg/3})
ensures that cell {\tt I} of the functor {\tt Term}
will be indirectly accessed (updated) even if it contains a variable
which in a WAM would be created  on place and therefore
it would be subject of unpredictable side-effects.

The reason of the draconian warning in some Prolog manuals
manual
\begin{quote}
...setarg is only safe if there is no further use
of the old value of the replaced argument...
\end{quote}.
will therefore disappear and a purely logical setarg
(with a {\em translation semantics} expressible in
term of {\tt setarg/4}) can be implemented.
Not only this ensures referential transparency
and allows normal
references to the old content of the updated
cells but it also makes incompatible implementations
of setarg (Sicstus, Eclipse, BinProlog) work exactly
the same way\footnote{A further ambiguity in some
implementations of {\tt setarg/3} comes from the fact
that it is not clear if the location itself or its
dereferenced contents should be mutated}.

To finish the job properly, something like the following ADT
can be created.

\begin{verbatim}
new_array(Size,Array):-
  functor(Array,'$array',Size).

update_array(Array,I,Val):-
  safe_setarg(I,Array,Val).

access_array(Array,I,Value):-
  safe_arg(I,Array,Value).
\end{verbatim}

We suggest to use this ADT in your program instead of basic setarg
when performance is not an absolute requirement.

A new {\tt change\_arg/3} builtin has been added to BinProlog to allow,
efficient failure-driven iteration with persistent information.
It works like {\tt setarg/3} except that side-effects are permanent.
Should unsafe heap objects be generated through the precess
{\tt change\_arg/3} signals a run-time error. This is not the case
as far the result is either a constant (which is does not need
new heap allocation) or the result of moving a preexistent
heap object to a new location.

For instance the (Haskell-style) {\tt fold/4} predicate 
(see {\tt library/high.pl}) uses {\tt change\_arg/3}  to avoid painful
iteration and slow side-effects on the dynamic database.
The implementation is competitive is speed
with hand-written explicitly recursive code and uses
only memory proportional to the size of the answer.
Alternatively, BinProlog  also implements a functional style
version of the same predicates, based on call/N (see help(fold)).

\begin{verbatim}
% fold,foldl based on safe failure driven destructive change_arg
foldl(Closure,Null,List,Final):-fold(Closure,Null,X^member(X,List),Final).

fold(Closure,Null,I^Generator,Final):-
  fold0(s(Null),I,Generator,Closure,Final).

fold0(Acc,I,Generator,Closure,_):-
  term_append(Closure,args(SoFar,I,O),Selector),
  Generator,
    arg(1,Acc,SoFar),
    Selector,
    change_arg(1,Acc,O),
  fail.
fold0(Acc,_,_,_,Final):-
  arg(1,Acc,Final).

?- foldl(+,0,[1,2,3],R).
?- fold(*,1,X^member(X,[1,2,3]),R).
\end{verbatim}


\section{Related work}

BinProlog related papers can be found following links from
\begin{verbatim}
    http://www.cs.unt.edu/~tarau
\end{verbatim}

{\flushleft The reader} interested in the internals of BinProlog and other
issues related to binary logic programs, their transformations
and performance evaluation is referred to
\cite{Tarau90:PLILP,Tarau91:JAP,Tarau91:RU,Demoen90:KUL,Demoen91:RU,Tarau92:WAMOpt,Tarau92:ECO,LOPSTR93:Neumerkel,Neum92,Tarau93:GULP,Tarau93a,kdb93f,WA83,lindgren,TD94:WE,TA94:JFPL,TN94:PLILP,pt93b,kdb93j,kdb93d,Demoen96:GC,TarauDF95,dbt95a,DPT96:PAP,TDF:asian96,lpnet96:virtual,tdb95rev}

Related BinProlog documentation is available at: 
\cite{bp7user,bp7advanced,bp7interface,bp7crossref}.

\bibliography{tarau,local}

%\input preds.tex

\end{document}
